原始题目:剑指 Offer 22. 链表中倒数第k个节点 (opens new window)
解题思路:
使用快慢指针解决这个问题。
一开始快慢指针 、 都指向链表表头,然后快指针 先走 步之后, 指针开始移动,两个指针同时移动。当 到达重点时, 指针刚好到达倒数第 个节点。
代码:
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null || k <= 0) {
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && k-- > 0) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复杂度分析
- 时间复杂度: 为链表的节点个数,因为 指针需要遍历全部的节点。
- 空间复杂度: 和 指针使用常数大小的额外空间。